#include <iostream>
#include <vector>
using namespace std;
/**
 * @brief 迭代版
 */
template<typename T> // 整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(<)的運算子功能
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}

// /**
//  * @brief 递归版
//  */
// void Merge(vector<int> &Array, int front, int mid, int end) {
//     // preconditions:
//     // Array[front...mid] is sorted
//     // Array[mid+1 ... end] is sorted
//     // Copy Array[front ... mid] to LeftSubArray
//     // Copy Array[mid+1 ... end] to RightSubArray
//     vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
//     vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
//     int idxLeft = 0, idxRight = 0;
//     LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
//     RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
//     // Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight], and put into Array[i]
//     for (int i = front; i <= end; i++) {
//         if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {
//             Array[i] = LeftSubArray[idxLeft];
//             idxLeft++;
//         } else {
//             Array[i] = RightSubArray[idxRight];
//             idxRight++;
//         }
//     }
// }

// void MergeSort(vector<int> &Array, int front, int end) {
//     if (front >= end)
//         return;
//     int mid = (front + end) / 2;
//     MergeSort(Array, front, mid);
//     MergeSort(Array, mid + 1, end);
//     Merge(Array, front, mid, end);
// }


/**
 * @brief 王道考研版--有问题
 */


// template<typename T> // 整數或浮点数皆可使用,若要使用物件(class)时必须设定"小于"(<)的运算子功能
// void Merge(T arr[], int len, int low, int mid, int high) {
//     T *B = new T[len];
//     // int *B = (int*)malloc(len*sizeof(int));  // 辅助数组B
//     int i, j, k;
//     for (k=low; k<=high; k++) {
//         B[k] = arr[k];        // 将所有元素复制到数组B中
//     }

//     for (i=low, j=mid+1, k=i; j<=mid&&j<=high; k++) {
//         if(B[i] <= B[j]){
//             arr[k] = B[i++];    // 将较小数复制到A
//         }
//         else{
//             arr[k] = B[j++];
//         }
//     }//for
//     while(i<=mid)  arr[k++] = B[i++];
//     while(j<=high) arr[k++] = B[j++];

//     delete[] B;
// }

// template<typename T> // 整數或浮点数皆可使用,若要使用物件(class)时必须设定"小于"(<)的运算子功能
// void MergeSort(T arr[], int len, int low, int high){
//     if(low<high) {
//         int mid = (low+high)/2;     //从中间划分
//         MergeSort(arr,len, low, mid);      //对左半边部分归并排序
//         MergeSort(arr,len, mid+1, high);   //对右半边部分归并排序
//         Merge(arr,len, low, mid,high);   //归并
//     }//if
// }


int main() {
    int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
    int len = (int) sizeof(arr) / sizeof(*arr);
    merge_sort(arr, len);
    
    // MergeSort(arr,len, 0, len-1);
    for (int i = 0; i < len; i++)
            cout << arr[i] << ' ';
    cout << endl;

    float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
    len = (float) sizeof(arrf) / sizeof(*arrf);
    merge_sort(arrf, len);
    // MergeSort(arrf,len, 0, len-1);
    for (int i = 0; i < len; i++)
            cout << arrf[i] << ", ";
    cout << endl;
    return 0;
}
